进化策略（ES）是一种基于自然进化概念的强大黑盒优化技术。在其每个迭代中，一个关键步骤都需要根据一些健身分数进行排名候选解决方案。对于增强学习的ES方法（RL），此排名步骤需要评估多个策略。目前是通过政策方法完成的：通过使用该策略与环境进行多次交互来估算每个政策的分数。这导致了很多浪费的互动，因为一旦排名完成，与排名最高的策略相关的数据仅用于后续学习。为了提高样品效率，我们基于适应性函数的局部近似，提出了一种新型的分支替代方案。我们在称为增强随机搜索（ARS）的最先进的ES方法的背景下演示了我们的想法。 Mujoco任务中的仿真表明，与原始ARS相比，我们的非政策变体具有相似的运行时间，即可达到奖励阈值，但仅需要70％左右的数据。它还胜过最近的信任区域。我们认为我们的想法也应该扩展到其他ES方法。

Q-learning and SARSA(0) with $\epsilon$-greedy exploration are leading reinforcement learning methods, and their tabular forms converge to the optimal Q-function under reasonable conditions. However, with function approximation, these methods exhibit strange behaviors, e.g., policy oscillation and chattering, convergence to different attractors (possibly even the worst policy) on different runs, etc., apart from the usual instability. Accordingly, a theory to explain these phenomena has been a long-standing open problem, even for basic linear function approximation (Sutton, 1999). Our work uses differential inclusion theory to provide the first framework for resolving this problem. We further illustrate via numerical examples how this framework helps explain these algorithms' asymptotic behaviors.

随机重球（SHB）和Nesterov的加速随机梯度（ASG）是随机优化的流行动量方法。尽管对确定性环境中这种加速思想的好处有充分的理解，但它们在随机优化方面的优势仍然尚不清楚。实际上，在某些特定情况下，众所周知，在样本复杂性意义上，动量无济于事。我们的工作表明，类似的结果实际上是整个二次优化的。具体而言，我们为该家族获得了SHB和ASG样品复杂性的下限，并表明Vanilla SGD可以实现相同的结合。我们注意到，存在二次优化中基于动量方法的优势的结果，但这些方法基于单方面或有缺陷的分析。

在多代理加固学习（MARL）中，多个代理商与普通环境相互作用，也与彼此相互作用，以解决连续决策中的共同问题。它在博彩，机器人，金融等中具有广泛的应用。在这项工作中，我们推导了一种在Marl中有用的分布式非线性随机近似方案的迭代对数的新规定。特别是，我们的结果描述了几乎每个样本路径上的收敛速度，其中算法会聚。这一结果是其分布式设置中的第一类，并提供比现有的更深层次的见解，它只讨论预期的收敛率或CLT感觉。重要的是，我们的结果在显着较弱的假设下保持：八卦矩阵都不需要是双随机的，也不是Spandsize Scalual。作为一个应用程序，我们表明，对于使用$ \ gamma \ In（0,1）中的步骤中的Spectize $ n ^ { - \ gamma} $，其中具有线性函数近似的分布式Td（0）算法具有$的收敛速度o（\ sqrt {n ^ { - \ gamma} \ ln n}）$ as;对于$ 1 / n $类型的步骤，同样是$ o（\ sqrt {n ^ { - 1} \ ln \ ln n}）$ a ..这些衰减率不依赖于描绘不同剂中相互作用的图表。

搜索引擎维护不同网页的本地副本，以提供快速搜索结果。此本地缓存由Web爬网程序保持最新，该Web爬网程序经常访问这些不同的页面以跟踪它们的变化。理想情况下，一旦页面上的页面更改，应更新本地副本。但是，有限带宽可用性和服务器限制限制了不同页面爬网的频率。这提出了以下优化问题：最大化本地缓存的新鲜度，这对爬网频率受到规定的界限。虽然存在易旧的算法来解决这个问题，但这些要么承担精确页面变化率的知识，也可以使用效率低效的方法，例如mle估计相同。我们在这里解决这个问题。我们提供了三个新颖的网页变更率的网上估计方案，所有这些方案都具有极低的速度迭代运行时间。第一个基于大量的规律，即在随机近似的第二个。第三是第二个的延伸，包括重球动量术语。所有这些方案只需要有关页面变更过程的部分信息，即，它们只需要知道页面是否已更改，自上次爬网实例以来。我们的主要理论结果涉及这三种方案的渐近收敛和收敛率。事实上，我们的作品是第一个显示原始随机重球方法的收敛，当梯度和噪声方差都不是均匀的界限时。我们还提供了一些数值实验（基于实际和合成数据），以证明我们提出的估算器的优越性，如现有的估计者。我们强调，我们的算法也很容易适用于数据库和网络库存管理的同步。